package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/24/22 12:39 AM
 * @question 37. 解数独
 * @description 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 */
public class SolveSudoku37 {

    public static void main(String[] args) {
        SolveSudoku37 test = new SolveSudoku37();
        char[][] demo = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        test.solveSudoku4(demo);
        for (char[] chars : demo) {
            System.out.println(Arrays.toString(chars));
        }
    }

    /**
     * 二进制+递归回溯
     * @param board
     */
    public void solveSudoku(char[][] board) {
        int temp;
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.'){
                    continue;
                }
                temp = (1 << (board[row][col] - 49));
                colTable[col] |= temp;
                rowTable[row] |= temp;
                blockTable[col / 3 + row / 3 * 3] |= temp;
            }
        }
        recursion(0, 0, board);
    }

    /**
     * 记录每列可用的数，二进制表示，下标代表数，值若为1则表示已用，为0则表示还没用
     */
    int[] colTable = new int[9];

    /**
     * 记录每行可用的数，二进制表示，下标代表数，值若为1则表示已用，为0则表示还没用
     */
    int[] rowTable = new int[9];

    /**
     * 记录每块可用的数，二进制表示，下标代表数，值若为1则表示已用，为0则表示还没用
     */
    int[] blockTable = new int[9];

    public boolean recursion(int row, int col, char[][] board){
        if (col < 9){
            if (row > 8 || board[row][col] != '.'){
                return recursion(row, col + 1, board);
            }
        }else if (row < 8){
            return recursion(row + 1, 0, board);
        }else {
            return true;
        }
//            availablePositions二进制表示时，所有的1表示该下标代表的数能用，依次遍历这些1,0x1ff相当于((1 << 9) - 1)
        int availablePositions = (~(colTable[col] | rowTable[row] | blockTable[col / 3 + row / 3 * 3])) & 0x1ff;
        while (availablePositions != 0){
//                取availablePositions二进制中最右边的 1 再组成二进制数，相当于 availablePositions &（~availablePositions +1）
            int num = availablePositions & (-availablePositions);
//            填数
            board[row][col] = (char)(Integer.toBinaryString(num).length() + 48);
//                把最低位的1置0
            availablePositions &= (availablePositions - 1);
//            指定处 置1  ->  val |= (1 << b);
            colTable[col] |= num;
            rowTable[row] |= num;
            blockTable[col / 3 + row / 3 * 3] |= num;
//            递归，如果成功则结束递归
            if (recursion(row, col + 1, board)){
                return true;
            }
//            失败了，开始回溯
//            指定处 置0  ->  val &= ~(1 << b);
            colTable[col] &= (~num);
            rowTable[row] &= (~num);
            blockTable[col / 3 + row / 3 * 3] &= (~num);
            board[row][col] = '.';
        }
        return false;
    }

    private boolean[][] line = new boolean[9][9];
    private boolean[][] column = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    private boolean valid = false;
    private List<int[]> spaces = new ArrayList<int[]>();

    /**
     * 官方-递归
     * @param board
     */
    public void solveSudoku2(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
//                   添加能放置数字的位置，方便遍历
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0);
    }

    public void dfs(char[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }

    private int[] line2 = new int[9];
    private int[] column2 = new int[9];
    private int[][] block2 = new int[3][3];
    private boolean valid2 = false;
    private List<int[]> spaces2 = new ArrayList<int[]>();

    /**
     *  官方-二进制+递归回溯
     * @param board
     */
    public void solveSudoku3(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces2.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        dfs2(board, 0);
    }

    public void dfs2(char[][] board, int pos) {
        if (pos == spaces2.size()) {
            valid2 = true;
            return;
        }
        int[] space = spaces2.get(pos);
        int i = space[0], j = space[1];
        int mask = ~(line2[i] | column2[j] | block2[i / 3][j / 3]) & 0x1ff;
        for (; mask != 0 && !valid2; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = Integer.bitCount(digitMask - 1);
            flip2(i, j, digit);
            board[i][j] = (char) (digit + '0' + 1);
            dfs2(board, pos + 1);
            flip2(i, j, digit);
        }
    }

    public void flip2(int i, int j, int digit) {
        line2[i] ^= (1 << digit);
        column2[j] ^= (1 << digit);
        block2[i / 3][j / 3] ^= (1 << digit);
    }

    private int[] line3 = new int[9];
    private int[] column3 = new int[9];
    private int[][] block3 = new int[3][3];
    private boolean valid3 = false;
    private List<int[]> spaces3 = new ArrayList<int[]>();

    /**
     * 官方-递归回溯+枚举
     * @param board
     */
    public void solveSudoku4(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }
        while (true) {
            boolean modified = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line3[i] | column3[j] | block3[i / 3][j / 3]) & 0x1ff;
//如果一个空白格只有唯一的数可以填入，也就是其对应的 b 值和 b-1 进行按位与运算后得到 0（即 b 中只有一个二进制位为 1）。此时，我们就可以确定这个空白格填入的数，而不用等到递归时再去处理它。
//                        因为mask-1就是把最右边的1置成0,如果mask只有一个1的话（也就是只有一个能放的数），置完之后就变成0了
                        if ((mask & (mask - 1)) == 0) {
                            int digit = Integer.bitCount(mask - 1);
                            flip(i, j, digit);
                            board[i][j] = (char) (digit + '0' + 1);
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) {
                break;
            }
        }

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces3.add(new int[]{i, j});
                }
            }
        }

        dfs3(board, 0);
    }

    public void dfs3(char[][] board, int pos) {
        if (pos == spaces3.size()) {
            valid3 = true;
            return;
        }

        int[] space = spaces3.get(pos);
        int i = space[0], j = space[1];
        int mask = ~(line3[i] | column3[j] | block3[i / 3][j / 3]) & 0x1ff;
        for (; mask != 0 && !valid3; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = Integer.bitCount(digitMask - 1);
            flip(i, j, digit);
            board[i][j] = (char) (digit + '0' + 1);
            dfs3(board, pos + 1);
            flip(i, j, digit);
        }
    }

    public void flip(int i, int j, int digit) {
        line3[i] ^= (1 << digit);
        column3[j] ^= (1 << digit);
        block3[i / 3][j / 3] ^= (1 << digit);
    }
}
